package org.jkuang.qstar.index.store;

import java.util.Arrays;
import java.util.Comparator;

import org.jkuang.qstar.index.iterator.SubList;

/**
 * 块区间
 *
 * 每个块区间的额定大小是 5万 最大可以达到10万，超过10万将进行断裂
 *
 *
 * @author star
 *
 */
public class DataBlock<T> {

	private volatile int size;
	private volatile T[] nodes;
	private Comparator<T> comparator;

	@SuppressWarnings("unchecked")
	public DataBlock(Comparator<T> comparator) {
		this.comparator = comparator;
		this.nodes = (T[]) new Object[0x0008];
	}

	/**
	 * 基于模板key找到到对应的对象
	 * 
	 * @param node
	 * @return
	 */
	public T get(T node) {
		int index = indexOf(node, SerarChType._index);
		if (index >= 0) {
			return nodes[index];
		} else {
			return null;
		}
	}

	/**
	 * 插入元素
	 *
	 * @param node
	 * @return
	 */
	public boolean insert(T node) {
		if (size == 0 || comparator.compare(node, nodes[size - 1]) > 0) {
			ensureCapacity(size + 1); // Increments modCount!!
			nodes[size++] = node;
			return true;
		} else {
			int index = indexOf(node, SerarChType._insert);
			if (index < 0) {
				// 如果元素已经存在
				nodes[- index -1] = node;
				return false;
			}
			ensureCapacity(size + 1);
			System.arraycopy(nodes, index, nodes, index + 1, size - index);
			nodes[index] = node;
			size++;
			return true;
		}
	}

	/**
	 * 删除元素
	 *
	 * @param node
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public boolean delete(T node) {
		int index = indexOf(node, SerarChType._index);
		if (index < 0) {
			return false;
		} else {
			int numMoved = size - index - 1;
			if (numMoved > 0) {
				T[] newNodes = ((T[]) new Object[size - 1]);
				System.arraycopy(nodes, 0, newNodes, 0, index);
				System.arraycopy(nodes, index + 1, newNodes, index, numMoved);
				size--;
				this.nodes = newNodes;
				return true;
			} else {
				this.nodes[--size] = null; // Let gc do its work
				return true;
			}
		}
	}

	/**
	 * 
	 * @param node 基于comparator 对比排序字段查找对应的位置
	 * @param type 大于等于node的，小于等于 node，插入位置，精确检索
	 * @return
	 */
	int indexOf(T node, SerarChType type) {
		int fromIndex = 0;
		int toIndex = this.size - 1;
		if (node == null) {
			return type == SerarChType._ceil ? fromIndex : toIndex;
		}

		while (fromIndex <= toIndex) {
			int mid = (fromIndex + toIndex) >> 1;
			int cmp = this.comparator.compare(nodes[mid], node);
			if (cmp < 0)
				fromIndex = mid + 1;
			else if (cmp > 0)
				toIndex = mid - 1;
			else
				return type == SerarChType._insert ? -(mid + 1) : mid; // key
																		// found
		}
		switch (type) {
		case _insert:
		case _ceil:
			return fromIndex;
		case _index:
			return -(fromIndex + 1);
		default:
			return toIndex;
		}
	}

	public int size() {
		return size;
	}

	/**
	 * 统计指定两个范围之间的数据总量（包含边界）
	 * 
	 * @param begin
	 * @param end
	 * @return
	 */
	public int size(T begin, T end) {
		int _s_index = 0;
		int _e_index = this.size - 1;
		if (begin != null && comparator.compare(begin, nodes[0]) > 0) {
			_s_index = indexOf(begin, SerarChType._ceil);
		}
		if (end != null && comparator.compare(end, nodes[size - 1]) < 0) {
			_e_index = indexOf(end, SerarChType._floor);
		}
		return _e_index - _s_index + 1;
	}

	/**
	 * 获取指定范围内的数据，以list（迭代器）的方式输出
	 *
	 * @param _begin
	 * @param _end
	 * @return
	 */
	public SubList<T> nodeList(T begin, T end, boolean desc) {

		int _s_index = indexOf(begin, SerarChType._ceil);
		int _e_index = indexOf(end, SerarChType._floor);
		return new SubList<T>(this.nodes, _s_index, _e_index, desc);
	}

	/**
	 * 检查目标元素是否在该数据块的范围内
	 *
	 * @param node
	 * @return
	 */
	public int rangeContains(T node) {
		// 在区间段的左边
		if (comparator.compare(nodes[size - 1], node) < 0) {
			return -1;
		} else if (comparator.compare(nodes[0], node) > 0) {
			return 1;
		} else {
			return 0;
		}
	}

	/**
	 * 数据量超过一定大小，则数据块分裂成两个块，避免在插入或删除数据的时候拷贝量过大
	 *
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public DataBlock<T>[] splitToTwo() {
		DataBlock<T>[] blocks = new DataBlock[2];
		int mid = this.size >> 1;
		blocks[0] = new DataBlock<T>(this.comparator);
		blocks[0].nodes = Arrays.copyOfRange(nodes, 0, mid);
		blocks[0].size = mid;

		blocks[1] = new DataBlock<T>(this.comparator);
		blocks[1].nodes = Arrays.copyOfRange(nodes, mid, this.size);
		blocks[1].size = this.size - mid;
		return blocks;
	}

	/**
	 * 检测容量，容量不足时候 自动进行扩容
	 *
	 * @param minCapacity
	 */
	public void ensureCapacity(int minCapacity) {
		int oldCapacity = nodes.length;
		if (minCapacity > oldCapacity) {
			int newCapacity = Math.min(oldCapacity >>> 1 + 1, 256) + oldCapacity;
			if (newCapacity < minCapacity) {
				newCapacity = minCapacity;
			}
			nodes = Arrays.copyOf(nodes, newCapacity);
		}
	}

}

enum SerarChType {
	_insert, _ceil, _index, _floor;
}
